package hot_problems_100;

public class P16_0041 {
    public int firstMissingPositive(int[] nums) {
        for(int i=0; i<nums.length; i++){
            if(nums[i]<=0 || nums[i]>= nums.length + 1){
                nums[i] = 0;
            }
        }
        for(int i=0; i<nums.length; i++){
            if(nums[i] > 0 && nums[i] <= nums.length){
                int new_index = nums[i] - 1;
                nums[i] = 0;
                while(nums[new_index] > 0){
                    int next_num = nums[new_index];
                    nums[new_index] = -1;
                    new_index = next_num - 1;
                }
                nums[new_index] = -1;
            }
        }
        for(int i=0; i<nums.length; i++){
            if(nums[i]>=0){
                return i+1;
            }
        }
        return nums.length + 1;
    }
}
